/*
 * @lc app=leetcode.cn id=349 lang=cpp
 *
 * [349] 两个数组的交集
 *
 * https://leetcode-cn.com/problems/intersection-of-two-arrays/description/
 *
 * algorithms
 * Easy (73.90%)
 * Likes:    506
 * Dislikes: 0
 * Total Accepted:    269.8K
 * Total Submissions: 365.1K
 * Testcase Example:  '[1,2,2,1]\n[2,2]'
 *
 * 给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
 * 
 * 
 * 
 * 示例 1：
 * 
 * 
 * 输入：nums1 = [1,2,2,1], nums2 = [2,2]
 * 输出：[2]
 * 
 * 
 * 示例 2：
 * 
 * 
 * 输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
 * 输出：[9,4]
 * 解释：[4,9] 也是可通过的
 * 
 * 
 * 
 * 
 * 提示：
 * 
 * 
 * 1 <= nums1.length, nums2.length <= 1000
 * 0 <= nums1[i], nums2[i] <= 1000
 * 
 * 
 */

// @lc code=start
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {

        //暴力解法
        // set<int> num1(nums1.begin(), nums1.end());
        // set<int> num2(nums2.begin(), nums2.end());
        
        // int length1 = num1.size(), length2 = num2.size();
        // vector<int> ans;

        // for(auto it = num1.begin(); it != num1.end(); it++){
        //     // int key = *it;
        //     for(auto jt = num2.begin(); jt != num2.end(); jt++){
        //         if(*it == *jt) ans.emplace_back(*it);
        //     }
        // }
        // return ans;


        // unordered_set<int> result_set; //存放结果
        // unordered_set<int> nums_set(nums1.begin(), nums1.end());
        // for(int num : nums2){
        //     //发现num2 的元素在 nums_set中出现过
        //     if(nums_set.find(num) != nums_set.end()){
        //         result_set.insert(num);
        //     }
        // }

        // vector<int> ans(result_set.begin(), result_set.end());
        // return ans;

        unordered_set<int> result_set;
        unordered_set<int> nums1_set(nums1.begin(), nums1.end());

        for(int nums : nums2){
            if(nums1_set.find(nums) != nums1_set.end()){
                result_set.insert(nums);
            }
        }

        return vector<int> (result_set.begin(), result_set.end());
    }
};
// @lc code=end

